package com.booby.algorithm.radix;

import com.booby.algorithm.utils.Utils;

import java.util.Arrays;

/**
 * 功能描述: 基数排序，从最低位开始 每位数采用稳定计数排序
 *
 * @author: lizt
 * @date: 2020/8/28 23:55
 **/

public class Lowest {

    public static final Integer[] arr = {4215,2403,1152,5326,3052,4308,1241};

    public static void sorted(Integer[] arr){
        // 整理数据，按照位数最多的来计算，不足则补0
        int maxLength = 4;
        for (int i = 0; i < maxLength; i++) {
            // 计算除数
            int division = (int)Math.pow(10, i);
            Integer[] count = new Integer[10];
            Arrays.fill(count, 0);
            // 计算每个数据中每位出现次数
            for (int j = 0; j < arr.length; j++) {
                int countIndex = arr[j] / division % 10;
                count[countIndex]++;
            }
            // count 累加数组
            for (int j = 1; j < count.length; j++) {
                count[j] += count[j-1];
            }
            // 还原数据
            Integer[] temp = new Integer[arr.length];
            for (int j = arr.length - 1; j >= 0; j--) {
                int index = arr[j] / division % 10;
                // 最后一位在原数组中的位置
                int tempIndex = count[index] - 1;
                temp[tempIndex] = arr[j];
                count[index]--;
            }
            // 覆盖原数组
            for (int j = 0; j < arr.length; j++) {
                arr[j] = temp[j];
            }
        }
    }
    public static void main(String[] args) {
        sorted(arr);
        Utils.print(arr);
    }
}
